package hot100;

import java.util.Arrays;

public class sortList {
    public mergeKLists.ListNode sortList(mergeKLists.ListNode head) {
        if(head == null) {
            return head;
        }

        int n = 0;
        mergeKLists.ListNode temp = head;
        while(temp != null) {
            n++;
            temp = temp.next;
        }
        int[] s = new int[n];
        int i = 0;
        while(head != null) {
            s[i] = head.val;
            i++;
            head = head.next;
        }
        Arrays.sort(s);
        mergeKLists.ListNode cur = new mergeKLists.ListNode(0);
        mergeKLists.ListNode ret = cur;
        for(i = 0;i < n;i++) {
            mergeKLists.ListNode tem = new mergeKLists.ListNode(s[i]);
            cur.next = tem;
            cur = cur.next;
        }
        return ret.next;

    }
}
